/**
 * 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。
 * 例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
 
    输入：00000000000000000000000000001011
    输出：3
    解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
 * 
 * 输入必须是长度为 32 的 二进制串 。
 */

// 1. 逐位判断 （时间复杂度 O(log2N)）
/**
 * 若 n & 1 = 0，则 n 二进制 最右一位 为 0 ；
 * 若 n & 1 = 1，则 n 二进制 最右一位 为 1 。
 */

var hammingWeight = function(n) {
    let res = 0;
    while (n) {
        res += n & 1;
        n >>>= 1; // 将n右移一位，左边补0，右边丢弃
    }
    return res;
};

// 2. 巧用n&(n−1)
/**
 * (n-1)解析： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。
 * n&(n−1) 解析： 二进制数字 n 最右边的 1 变成 0 ，其余不变。
 *
 */
var hammingWeight = function(n) {
    let res = 0;
    while (n) {
        res += 1;
        n &= n - 1;
    }
    return res;
};